package 算法;

import org.omg.Messaging.SYNC_WITH_TRANSPORT;

import javax.jws.soap.SOAPBinding;
import java.util.*;

public class Solution {

    public void putHas(HashMap<Integer,Set<Integer>> hashMap,Integer key,Integer val){
        if(hashMap.containsKey(key)){
            Set<Integer> set = hashMap.get(key);
            set.add(val);
        }
    }
    public boolean canCross(int[] stones) {
        if(stones[1] !=1) return false;
        HashMap<Integer, Set<Integer>> hashMap = new HashMap<>();
        for (int stone : stones) {
            hashMap.put(stone,new HashSet());
        }
        putHas(hashMap,stones[1],1);
        int i = 1;
        int len = stones.length;
        int cc = stones[len-1];
        for (; i < len; i++) {
            int j = stones[i];
            Set<Integer> set = hashMap.get(j);
            if(set.size() == 0 && j == cc)break;
            for (Integer integer : set) {
                putHas(hashMap,j+integer,integer);
                putHas(hashMap,j+integer+1,integer+1);
                if(integer-1 != 0)
                    putHas(hashMap,j+integer-1,integer-1);
            }
        }
        if(i < len) return false;
        return true;
    }
    public static void main(String[] args) {
        System.out.println(new Solution().largestSumOfAverages(new int[]{2,4,2},2));
    }
    public double probabilityOfHeads(double[] prob, int target) {
        int len = prob.length;
        double[][] dp = new double[target+1][len];

        double sum = 1;
        for (int i = 0;i < len;i++){
            sum *= (1-prob[i]);
            dp[0][i] = sum;
        }
        for (int i = 1; i <= target;i++){
            for (int i1 = i;i1 < len;i1++){
                dp[i][i1] = prob[i1]*dp[i-1][i1-1];
            }
        }
        return dp[target][len];
    }
    public int minCost(int[][] costs) {
        int len = costs.length; //len个房子
        int kcolor = costs[0].length; //k个颜色
        int[][] val = new int[kcolor][len];
        for(int i = 0; i < kcolor; i++){
            val[i][0] = costs[0][i];
        }
        for (int i = 1; i < len; i++) {
            for (int i1 = 0; i1 < kcolor;i1++){
                int min = Integer.MAX_VALUE;
                for (int i2 = 0; i2 < kcolor;i2++){
                    if(i1 != i2 && val[i2][i-1] < min) min = val[i2][i-1];
                }
                val[i1][i] = costs[i][i1]+min;
            }
        }
        int res = Integer.MAX_VALUE;
        len = len-1;
        for (int i = 0; i < kcolor; i++){
            if(res > val[i][len])
            res = val[i][len];
        }
        return res;
    }
    public int superEggDrop(int K, int N) {
        int res = 0;
        while (K>1){
            if(N == 1) return res;
                    res++;
            int midd = N/2;
            N = Math.max(N-midd,midd-1);

        }
        return res+N-1;
    }
    public double largestSumOfAverages(int[] A, int K) {
        int len = A.length;
        Double[][] dp = new Double[K][len];

        int sum = 0;
        for (int i = 0;i < len; i++){
            sum+=A[i];
            dp[0][i] = 1.0*sum / (i+1);
        }
        for (int k = 1; k < K; k++){
            for (int n = k; n < len; n++){
                dp[k][n] = 0.0;
                sum = 0;
                for (int j = n; j > k-1 ;j--){
                    sum+=A[j];
                    double i2 = dp[k][n];
                    double i3 = 1.0*sum/(n-j+1)+dp[k-1][j-1];
                    dp[k][n] = Math.max(dp[k][n],1.0*sum/(n-j+1)+dp[k-1][j-1]);
                }
            }
        }
        return dp[K-1][len-1];
    }

    public ListNode insertionSortList(ListNode head) {
        ListNode ln = new ListNode(Integer.MIN_VALUE);

        ListNode top = ln;
        while (head != null){
            if(top.next == null){
                top.next = new ListNode(head.val);
            }else if(top.next.val < head.val){
                top = top.next;
            }else {
                ListNode temp = top.next;
                top.next = new ListNode(head.val);
                top.next.next =temp;
                top = ln;
                head = head.next;
            }
        }

        return ln.next;
    }
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int len = stations.length;
        int[][] val = new int[len+1][2];
        if(target < stations[0][0])
            return -1;
        for (int i = 1; i < len; i++) {
            val[i][1] = val[i-1][1];
            while (startFuel < stations[i][0]){
                //在每加油的加油站找油最多的一个
                int ful = minRefuel(stations,val,i-1);
                if(ful == -1) return -1;
                startFuel+=ful;
                val[i][1]++;
            }
        }
        int i = val[len-1][1];
        while (startFuel < target){
            //在每加油的加油站找油最多的一个
            int ful = minRefuel(stations,val,i-1);
            if(ful == -1) return -1;
            startFuel+=ful;
            i++;
        }
        return i;
    }
    public int minRefuel(int[][] stations,int[][] val,int n){
        int maxFult = 0;
        int maxIndex = 0;
        for (int i = 0; i <= n; i++){
            //说明油站没加过油
            if(val[i][0] == 0){
                if(stations[i][1] > maxFult){
                    maxFult = stations[i][1];
                    maxIndex = i;
                }
            }
        }
        if(maxFult == 0)return -1;
        val[maxIndex][0]=1; //表示此油站加过油
        return maxFult;
    }
    public int[] countBits(int num) {
        int[] a = new int[num+1];
        for (int i = 1; i < a.length; i++) {
            a[i] = hammingWeight(1);
        }
        return a;
    }
    public int hammingWeight(int n) {
        int res = 0;
        int i = 1;
        for (int j = 0;j<=32;j++){
            if((i<<j&n)!=0){
                res++;
            }
            i = i<<1;
        }
        return res;
    }
    public int longestCommonSubsequence(String text1, String text2) {
        text1.length();
        int l1 = text1.length();
        int l2 = text2.length();
        int[][] dp = new int[l1+1][l2+1];
        for(int i = 1; i <= l1; i++){
            for(int i1 = 1; i1 <= l2; i1++){
                if(text1.charAt(i-1) == text2.charAt(i1-1)){
                    dp[i][i1] = 1+dp[i-1][i1-1];
                }else {
                    dp[i][i1] = Math.max(dp[i][i1-1],dp[i-1][i1-1]);
                }
            }
        }
        return dp[l1][l2];
    }

    public int countPrimes1(int n) {
        int res = 0;
        if(n <= 2) return res;
        res++; //2是素数据
        if(n>=3) res++;
        for (int i = 4; i < n; i++) {
            int mid = i/2;
            int j;
            for(j = 2; j <= mid;j++){
                if(i%j == 0){
                    break;
                }
            }
            if(j>mid)
                res++;
        }
        return res++;
    }

    //统计所有小于非负整数n的质数的数量
    public int countPrimes(int n) {
        int res = 0;
        if(n < 2) return res;
        res++; //2是素数据
        for (int i = 3; i <= n; i++) {
            int mid = i/2;
            int j;
            for(j = 2; j < mid;j++){
                if(i%j == 0){
                    break;
                }
            }
            if(j==mid)
            res++;
        }
        return res++;
    }
    //将零移动到最后
    public void moveZeroes(int[] nums) {
        int left,right;
        left=right=0;
        int i = nums.length;
        while (right < i){
            if(nums[right] != 0){
                int t = nums[left];
                nums[left] = nums[right];
                nums[right] = t;
                left++;
            }
            right++;
        }
        left+=1;
        while (left < i){
            nums[left++]=0;
        }
    }
    public int trap(int[] height){
        int res = 0;
        while (true){
            res += shui1(height);
            int i = Integer.MAX_VALUE;
            for (int i1 : height) {
                if(i1 == 0) continue;
                if(i1<i) {
                    i = i1;
                }
            }
            if(i == Integer.MAX_VALUE) break;
            for (int i1 = 0; i1 < height.length; i1++) {
                if(height[i1] != 0)
                    height[i1] -= i;
            }

        }
        return res;
    }
    public int shui1(int[] height){
        int len = height.length;
        int[] shui = new int[len];
        int j = height[0] != 0 ? 0:-1; //代表上一个块的位置
        int k3 = 1; //最小填充块
        for (int i = 1; i < len; i++) {
            if(height[i]==0){
                shui[i] = shui[i-1];
            }else {
                if(j == -1)shui[i]=shui[i-1];
                else {
                    shui[i]=(i-j-1)*Math.min(height[i],height[j])+shui[i-1];
                    //[j,i]中的0填充下标，并记录下标
                    int k1 = j+1;
                    int k2 = Math.min(height[i],height[j]);

                    while (k1<i){
                        height[k1++] = k2;
                    }
                }

                j=i;
            }
        }
        return shui[len-1];
    }
    public int trap1(int[] height) {
        int res = 0;
        boolean bl = true;
        while (bl){
            bl = false;
            int i = shui(height);

            res += i;
            for (int i1 = 0; i1 < height.length; i1++) {
                if(height[i1] != 0){
                    height[i1]--;
                    bl = true;
                }
            }
        }


        return res;
    }
    public int shui(int[] height){
        int i = 0;
        int res = 0;
        while (i < height.length){
            if(height[i] != 0) break;
            i++;
        }
        if(i == height.length) return res;
        while (i < height.length-1){
            int j = i++;
            while (i < height.length){
                if(height[i] != 0) break;
                i++;
            }
            if(i == height.length) return res;
            res += i-j-1;
        }
        return res;
    }
    public int numDecodings(String s) {
//        int[] val = new int[s.length()];
//        if(s.charAt(0)!='0')val[0] = 1;
//        int l = s.length();
//        int j = 0;
//        char a  = s.charAt(1);
//        char b  = s.charAt(0);
//        if(a=='0') val[1] = val[0];
//        else {
//            if(a!='0') j = val[0]+1;
//            if(b == '1' || (b=='2' && a != '0' && a <= '6'))j++;
//            val[1] = j;
//        }
//
//
//        for (int i = 2; i < l; i++){
//            int j1 = val[i-1];
//            char a  = s.charAt(i);
//            char b  = s.charAt(i-1);
//            if(a != '0') j1++;
//            int j2 = val[i-2];
//            if(b=='1') j2++;
//            else if(b=='2' && a <= '6') j2++;
//            val[i] = Math.max(j1,j2);
//        }
//        return val[l-1];
        return 0;
    }
    public int numberOfArithmeticSlices(int[] A) {
        int l = A.length;
        int[] val = new int[l];
        int sub = Integer.MIN_VALUE;
        for (int i = 1; i < l; i++) {
            if(A[i]-A[i-1] == sub){
                val[i] = val[i-1]+1;
            }else {
                val[i] = 0;
            }
            sub = A[i] - A[i-1];
        }
        int res = 0;
        for (int i = val.length - 1; i >= 0; ) {
            int a = val[i]+2;
            while (val[--i]+2 < a){};
            int j = 3;

            while (j<=a){
                res += a-j+1;
                j++;
            }

        }

        return res;
    }
    public int shortestWay(String source, String target) {
        HashMap<Character,Integer> ha = new HashMap<>();
        int i = source.length();
        for(int j = 0; j < i; j++){
            ha.put(source.charAt(j),j);
        }
        int max = 1;
        if(!ha.containsKey(target.charAt(i-1))){
            return -1;
        }
        int c = ha.get(target.charAt(i-1));
        for (int j = target.length()-2;j>=0;j--){
            int c2 = ha.get(target.charAt(j));
            if(c2 >= c){
                max++;
            }
            c = c2;
        }
        return max;
    }
    public int longestValidParentheses(String s) {

        int[] rs = new int[s.length()];
        int i = s.length();
        for(int j = 0; j < i; j++){
            if(s.charAt(j) == ')'){
                //找到前边有效的（
                int k = j-1;
                while (k >= 0){
                    if(s.charAt(k) == '('){
                        break;
                    }else {
                        k = k - rs[k];
                    }
                }
                if(k >= 0){
                    rs[j] = j-k+1 + (k-1>=0?rs[k-1]:0);
                }
            }
        }
        int imax = 0;
        for (int r : rs) {
            if(r>imax) imax=r;
        }
        return imax;
    }
    public int lenLongestFibSubseq(int[] A) {
        int[] a = new int[A.length];
        int res = 0;


        return res;

    }
}